/**
 * 插入排序
 * 选择未排序的第一个元素
 * 将该元素插入到已排序它该在的位置
 */
public class InsertSort {

    /**
     * 交换数组下标i和j的值
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[] nums,int i,int j){
        if (nums==null||i==j)
            return;
        if(i>nums.length||j>nums.length){
            throw new ArrayIndexOutOfBoundsException("数组下标越界");
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void sort(int[] nums){
        if(nums==null||nums.length<=0)
            return;

        for (int i = 1; i < nums.length; i++) {
            int k=i;
            for (int j = i; j >=0 ; j--) {
                if(nums[k]<nums[j]){
                    swap(nums,k,j);
                    k=j;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {0,-9,11,5,2,9,18,3,6};
        InsertSort insertSort = new InsertSort();
        insertSort.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
